#include "symmetricpolynomial.h"
#include "GenericPermutation.h"
#include "Multinomial.cpp"
#include "Fraction.h"
#include<algorithm>
#include<iostream>

template<typename T>
void print_vec(T vec){
     typename T::iterator it = vec.begin();
     if(it!=vec.end()){
         std::cout<<"["<<*it;
         ++it;
     }
     else return;
     for(;it!=vec.end();++it){
         std::cout<<","<<*it;
     }
     std::cout<<"]";
}
//Test function to print the values of map
template<typename T, typename R>
void print_map(std::map<T,R> mp){
    std::map<std::vector<int>,fraction<int> >::iterator it = mp.begin();
    for(;it!=mp.end();++it){
        std::vector<int> tmp = it->first;
        std::vector<int>::iterator it_vec = tmp.begin();
        std::cout<<"\t\tmap[";
        if(it_vec!=tmp.end()) std::cout<<*it_vec++;
        for(;it_vec!=tmp.end();++it_vec){
            std::cout<<","<<*it_vec;
        }
        std::cout<<"]="<<it->second<<std::endl;
    } 
}
//Some prototypes of foreign functions used in fraction scope
template<typename T, typename collection>
int count_combination_terms(collection deg, int numb_vars);
//Default constructor results in an empty polynomial which can be added to anyone
/*template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
symmetricpolynomial(){
}*/

/*//Null polynomial in specified variables - defined in header file
template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
symmetricpolynomial(varsType varList) : vars(varList){
}*/

/*template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
symmetricpolynomial(degreeType deg, T coeff){
    if(deg.size()>0){
        T z(0);
        
    }
}*/

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
symmetricpolynomial(degreeType deg, varsType variables, T coeff) : vars(variables){
    if(deg.size()>variables.size())
      throw typename symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
            symmetricpolynomial_exception();
    std::sort(deg.begin(),deg.end());
    symmDegree[deg] = coeff;
    clean_excedentary();
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
symmetricpolynomial(degreeStructureType symm, varsType variables) : vars(variables), symmDegree(symm){
    typename degreeStructureType::iterator it = symm.begin();
    for(;it!=symm.end();++it){
        if((it->first).size()>vars.size())
            throw typename symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
                symmetricpolynomial_exception();
    }
    clean_excedentary();
}

/*template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
symmetricpolynomial(const symmetricpolynomial& right){
}*/

//Some public functions
template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
add(symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>& right){
    if(!compare_vars(this->vars,right.vars))
        throw typename symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
                symmetricpolynomial_exception();
    symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits> res(*this);
    T z(0);  //To avoid nulls
    typename degreeStructureType::iterator it = right.symmDegree.begin();
    for(;it!=right.symmDegree.end();++it){
        if((it->second)!=z)
          res.add_mon(it->first,it->second);
    }
    return res;
}

//Multiply the symmetric polynomial
template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
multiply(symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>& right){
    if(!compare_vars(this->vars,right.vars))
        throw typename symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
                symmetricpolynomial_exception();
    symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits> res(right.get_vars());
    res.vars = this->vars;
    //Declares a variable temp to contain the result as a map
    degreeStructureType temp;
    std::map<degreeType,fraction<int> > temp1;
    //Get an iterator to symmetric polynomial hash representation
    typename degreeStructureType::iterator it1 = (*this).symmDegree.begin();
    for(;it1 != (*this).symmDegree.end();++it1){
         typename degreeStructureType::iterator it2 = right.symmDegree.begin();
         for(;it2 != right.symmDegree.end();++it2){
                  temp1 = multiply_monomial(it1->first,it2->first);
                  temp = multiply_constant(temp1,it1->second*it2->second);
                  res.add_set(temp);
         }  
    }
    return res;
}

//Multiply this by a constant
template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
multiply_constant(T& right){
    symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits> res(*this);
    degreeStructureType tmp = multiply_constant(symmDegree,right);
    res.vars = varsType(vars);  //get a cooy of vars
    res.symmDegree = tmp;
    return res;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
int
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
degree(){
    int res = 0;
    int temp;
    typename degreeStructureType::iterator it = symmDegree.begin();
    for(;it!=symmDegree.end();++it){
        temp = 0;
        degreeType v = it->first;
        typename degreeType::iterator it1 = v.begin();
        for(;it1!=v.end();it1++) temp += *it1;
        if(temp>res) res = temp;
    }
    return res;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
T
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
lcoeff(){
    T f(0);
    T zt(0);
    int res = 0;
    int temp;
    typename degreeStructureType::iterator it = symmDegree.begin();
    for(;it!=symmDegree.end();it++){
        temp = 0;
        degreeType v = it->first;
        typename degreeType::iterator it1 = v.begin();
        for(;it1!=v.end();it1++) temp += *it1;
        if(temp>=res){
            if(it->second!=zt){
                f = it->second;
                res = temp;
            }
        }
    }
    return f;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
degreeType
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
ldegree(){
    degreeType deg;
    int res = 0;
    int temp;
    typename degreeStructureType::iterator it = symmDegree.begin();
    for(;it!=symmDegree.end();it++){
        temp = 0;
        degreeType v = it->first;
        typename degreeType::iterator it1 = v.begin();
        for(;it1!=v.end();it1++) temp += *it1;
        if(temp>res){
            deg = it->first;
            res = temp;
        }
    }
    return deg;    
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
bool
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
is_empty(){
    return (symmDegree.size() == 0);
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
varsType
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
get_vars(){
    return this->vars;
}

//Operator overloading
template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
operator+(symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits> right){
    return add(right);
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
operator*(symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits> right){
    return multiply(right);
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
operator-(symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>& right){
    symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits> temp(right);
    T sm(-1);
    symmetricpolynomial temp1(temp.multiply_constant(sm));
    return *this + temp1;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>&
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
operator=(symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>& right){
    symmDegree = right.symmDegree;
    vars = right.vars;
    return *this;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
bool
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
operator==(symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>& right){
    if(!compare_vars(vars,right.vars)) return false;
    return (symmDegree == right.symmDegree);
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
bool
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
operator!=(symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>& right){
    return !(*this == right);
}

template<typename R, typename V, typename D, typename DS, typename Traits>
std::istream& operator>>(std::istream& is, symmetricpolynomial<R,V,D,DS,Traits>& sp){
    return sp.read(is);
}

template<typename R, typename V, typename D, typename DS, typename Traits>
std::ostream& operator<<(std::ostream& os, symmetricpolynomial<R,V,D,DS,Traits> sp){
    sp.write(os);
    return os;
}

//Private functions
template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
void
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
clean_excedentary(){
    degreeStructureType temp(symmDegree);
    typename degreeStructureType::iterator it = temp.begin();
    for(;it!=temp.end();++it)
        if((it->second)==T(0)) symmDegree.erase(it->first);
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
void
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
add_mon(degreeType deg, T coeff){
    if(deg.size()>vars.size())
      throw typename symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
                symmetricpolynomial_exception();
    T z(0);
    std::sort(deg.begin(),deg.end());
    typename degreeStructureType::iterator it = symmDegree.find(deg);
    if(it!=symmDegree.end()){
        it->second = (it->second) + coeff;
        if((it->second) == z)  symmDegree.erase(it);
    }
    else{
        degreeType tmp;
        bool has_list = false;
        typename degreeStructureType::iterator it = symmDegree.begin();
        for(;it!=symmDegree.end();++it){
            has_list = same_list(it->first,deg);
            if(has_list){
                tmp = it->first;
                break;
            }
        }
        if(!has_list) symmDegree[deg] = coeff;
        else{
             it->second = (it->second) + coeff;
             if((it->second) == z) symmDegree.erase(it);
        }
    }
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
bool
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
same_list(degreeType deg1, degreeType deg2){
    sort(deg1.begin(),deg1.end());
    sort(deg2.begin(),deg2.end());
    bool res = true;
    if(deg1.size()>deg2.size()){
        for(int i=0; i<deg2.size(); i++)
                if(deg2[i] != deg1[i]){
                    res = false;
                    break;
                }
    }
    else{
        for(int j=0; j<deg1.size(); j++)
                if(deg2[j] != deg1[j]){
                    res = false;
                    break;
                }
    }
    return res;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
void
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
add_set(degreeStructureType dst){
    typename degreeStructureType::iterator it = dst.begin();
    for(;it!=dst.end();it++){
        add_mon(it->first,it->second);
    }
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
bool
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
compare_vars(varsType vrs1, varsType vrs2){
    bool res = true;
    if(vrs1.size()==0) return false;
    if(vrs2.size()==0) return false;
    typename varsType::iterator it_left = vrs1.begin();
    for(;it_left!=vrs1.end();it_left++){
        bool res1 = false;
        typename varsType::iterator it_right = vrs2.begin();
        for(;it_right!=vrs2.end();it_right++){
            if(*it_left == *it_right) res1 = true;
        }
        if(!res1) return false;
    }
    return res;
}

//This function is not type secure once degreeType must be some collection of integers
//That can be solved by a foreign template function
template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
int
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
count_terms(degreeType deg, int numb_vars){
    return count_combination_terms<int,degreeType>(deg,numb_vars);    
}
//Foreign function
template<typename T, typename collection>
int count_combination_terms(collection deg, int numb_vars){
    std::map<T,int> mp_counter;
    typename collection::iterator it = deg.begin();
    for(;it != deg.end();++it) mp_counter[*it]++;
    if(deg.size()<numb_vars) mp_counter[T(0)] += numb_vars - deg.size();
    typename std::map<T,int>::iterator mp_iter = mp_counter.begin();
    collection temp;
    for(;mp_iter!=mp_counter.end();++mp_iter)
        temp.push_back(mp_iter->second);
    multinomial<int,collection> res(numb_vars,temp);
    return res.get_result();
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
degreeStructureType
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
multiply_constant(degreeStructureType& dst, T cnst){
    degreeStructureType res(dst);
    typename degreeStructureType::iterator it = res.begin();
    for(;it!=res.end();++it)
        res[it->first] = res[it->first] * cnst;
    return res;
}
//To multiply constat with map<int,fraction<int> >
template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
degreeStructureType
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
multiply_constant(std::map<degreeType,fraction<int> >& dst, T cnst){
    degreeStructureType res;
    std::map<degreeType,fraction<int> > temp(dst);
    typename std::map<degreeType,fraction<int> >::iterator it = temp.begin();
    for(;it!=temp.end();++it){
        int i = (temp[it->first]).get_numerator();
        res[it->first] = cnst * T(i);
    }  //const must multiply with fraction<int>
    return res;
}
/* The function used to multiply symmetric monomials is use the permutation
 * iterator. It is one of the most interesting examples of such iterator's
 * applications in practice.
 */
template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
std::map<degreeType,fraction<int> >
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
multiply_monomial(degreeType deg1, degreeType deg2){
                                 //std::cout<<"@multiply_monomial"<<std::endl;
    std::map<degreeType,fraction<int> > res;
    int n1 = count_terms(deg1,vars.size());
    int n2 = count_terms(deg2,vars.size());
    int n;
    degreeType temp1, temp2;
    if(n1<=n2){
               temp1 = deg1;
               temp2 = deg2;
               n = n2;
    }
    else{
         temp1 = deg2;
         temp2 = deg1;
         n = n1;
    }
    for(int i = temp1.size();i<vars.size();++i) temp1.push_back(0);
    //At this point we use the generic permutation iterator to multiply the monomials
    //We are going to assume that vector type is a collection of integers
    GenericPermutation<int,degreeType> gpC(temp1);
    typename GenericPermutation<int,degreeType>::iterator gp_iterator = gpC.begin();
    //std::cout<<"\tEntering permutation cicle"<<std::endl;
    for(;gp_iterator!=gpC.end();++gp_iterator){
                                               //std::cout<<"\t\t\t";
                 //print_vec<degreeType>(*gp_iterator);
                 //std::cout<<std::endl;
        degreeType s_degree = sum_degree(*gp_iterator,temp2);
        sort(s_degree.begin(),s_degree.end());
        int tot = count_terms(s_degree,vars.size());
        if(res.find(s_degree)==res.end()){
            bool has_list = false;
            typename std::map<degreeType,fraction<int> >::iterator it = res.begin();
            degreeType tmp;
            for(;it!=res.end();++it){
                has_list = same_list(it->first,s_degree);
                if(has_list){
                    tmp = it->first;
                    break;
                }
            }
            fraction<int> t(n,tot);
            if(!has_list){   
                res[s_degree] = t;
            }
            else{
                     //It must be possible to add an element of type T with a fraction of intergers
                 fraction<int> fi = res[tmp] + t;
                 res[tmp] = fi;
                 fraction<int> zf(0);
                 if(fi==zf) res.erase(tmp);
            }
        }
        else{
             //It must be possible to add an element of type T with a fraction of intergers
             fraction<int> fi_t(n,tot);
             fraction<int> ftemp = res[s_degree] + fi_t;
             res[s_degree] = ftemp;
             fraction<int> zf_t(0);
             if(res[s_degree]==zf_t) res.erase(s_degree);
        }
    }
    /*std::cout<<"res=";
    print_map<std::vector<int>,fraction<int> >(res);
    std::cout<<"deg1=";
    print_vec<std::vector<int> >(deg1);
    std::cout<<std::endl<<"deg2=";
    print_vec<std::vector<int> >(deg2);
    std::cout<<std::endl;*/
    return res;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
degreeType
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
sum_degree(degreeType deg1, degreeType deg2){
    degreeType res;
    typename degreeType::iterator it1 = deg1.begin();
    typename degreeType::iterator it2 = deg2.begin();
    if(deg1.size()<=deg2.size()){
        for(;it1!=deg1.end();++it1){
            res.push_back(*it1 + *it2);
            it2++;
        }
    }
    else{
        for(;it2!=deg1.end();++it2){
            res.push_back(*it1 + *it2);
            it1++;
        }
    }
    return res;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
std::istream&
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
read(std::istream& is){
    return is;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
std::ostream&
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::
write(std::ostream& os){
    if(symmDegree.size()==0){
        os<<T(0);
        return os;
    }
    typename degreeStructureType::iterator it = symmDegree.begin();
    if(it!=symmDegree.end()){
        degreeType dt = it->first;
        get_symm_mon(os,dt,it->second);
        ++it;
    }
    for(;it!=symmDegree.end();++it){
        os<<"+";
        degreeType dt = it->first;
        get_symm_mon(os,dt,it->second);
    }
}

/*//Some write auxiliary functions
template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
std::string to_string(){
}*/

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
std::ostream& 
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::get_var_deg(std::ostream& os,varsType& vrs,degreeType deg){
    typename degreeType::iterator it = deg.begin();
    typename varsType::iterator it_vars = vrs.begin();
    for(;it!=deg.end();++it){
        if(*it!=0){
            if(*it==1) os<<*it_vars;
            else os<<*it_vars<<"^"<<*it;
        }
        ++it_vars;
    }
    return os;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
std::ostream& 
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::get_symm_mon(std::ostream& os,degreeType& deg, T& coeff){
    GenericPermutation<int,degreeType> gp(deg);
    typename GenericPermutation<int,degreeType>::iterator it = gp.begin();
    //The first time there is no need to stream out a "+" char
    if(it!=gp.end()){
        if(coeff == T(1)){
            if(!is_const_monomial(*it)){
                get_var_deg(os,vars,*it);
            }
            else os<<coeff;
        }
        else if(coeff!=T(0)){
             os<<coeff;
             get_var_deg(os,vars,*it);
        }
        else os<<coeff;
        ++it;
    }
    for(;it!=gp.end();++it){
        os<<"+";
        if(coeff == T(1)){
            if(!is_const_monomial(*it)) get_var_deg(os,vars,*it);
            else os<<coeff;
        }
        else if(coeff!=T(0)){
             os<<coeff;
             get_var_deg(os,vars,*it);
        }
        else os<<coeff;
    }
    return os;
}

template<typename T, 
         typename varsType, 
         typename degreeType,
         typename degreeStructureType,
         typename traits>
bool 
symmetricpolynomial<T,varsType,degreeType,degreeStructureType,traits>::is_const_monomial(degreeType deg){
    typename degreeType::iterator it = deg.begin();
    for(;it!=deg.end();++it){
        if(*it!=0) return false;
    }
    return true;
}

